﻿//----------------------------------------------------------
///---------c LinkList--------------------------------------
///---------12/5/2021---- by----mky.蒙克雨------------------
//----------------------------------------------------------
#include "BasicLinkList.hpp"
#include "LinkList.h"

//----------------------------------------------------------
LinkListNode* InitLinkList(void)
{
	LinkListNode* pHead = nullptr;
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	if (pHead != nullptr)
		pHead->pNext = nullptr;

	return pHead;
}

//----------------------------------------------------------
int GetSizeLinkList(LinkListNode* pHead)
{
	int num = 0;
	while (pHead->pNext != nullptr)
	{
		pHead = pHead->pNext;
		num++;
	}
	return num;
}

//----------------------------------------------------------
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos)
{
	LinkListNode* pNode = nullptr;
	int num = 0;
	while (num < pos && pHead->pNext != nullptr)
	{
		pNode = pHead->pNext;
		num++;
	}

	if (num == pos)
	{
		return pNode;
	}
	else
	{
		return nullptr;
	}
}

//----------------------------------------------------------
LinkListNode* LocateLinkList(LinkListNode* pHead, ElemType objData)
{
	while (pHead->pNext != nullptr)
	{
		pHead = pHead->pNext;
		if (pHead->data == objData)
			return pHead;
	}

	return nullptr;
}

//----------------------------------------------------------
LinkListNode* Create_Rear_LkList(ElemType arr[], int length)
{
	LinkListNode* pHead = nullptr;//头节点
	LinkListNode* pAddNode = nullptr;//新增节点
	LinkListNode* qMoveFlag = nullptr;//移动标志位
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));

	qMoveFlag = pHead;//尾插法 标志位始终处于链表的尾部
	for (int num = 0; num < length; num++)
	{
		pAddNode = (LinkListNode*)malloc(sizeof(LinkListNode));
		pAddNode->data = arr[num];

		qMoveFlag->pNext = pAddNode;//标志位指向新节点
		qMoveFlag = pAddNode;//标志位后移
	}
	qMoveFlag->pNext = nullptr;
	return pHead;
}

//----------------------------------------------------------
LinkListNode* Create_Front1_LkList(ElemType arr[], int length)
{
	LinkListNode* pHead = nullptr;//头节点
	LinkListNode* pAddNode = nullptr;//新增节点
	LinkListNode* qMoveFlag = nullptr;//移动位
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = nullptr;
	//头插法 头节点始终指向标志位
	qMoveFlag = pHead->pNext;//关系位存入头结点下一位
	for (int num = length - 1; num >= 0; num--)
	{
		pAddNode = (LinkListNode*)malloc(sizeof(LinkListNode));
		pAddNode->data = arr[num];

		pAddNode->pNext = qMoveFlag;//是的新加入的节点传入了上一个节点
		pHead->pNext = pAddNode;//头节点指向了当前的新加入节点
		qMoveFlag = pAddNode;//让pMoveHead指向当前的节点
	}
	return pHead;
}

//----------------------------------------------------------
LinkListNode* Create_Front2_LkList(ElemType arr[], int length)
{
	LinkListNode* pHead = nullptr;//头节点
	LinkListNode* pAddNode = nullptr;//新增节点
	LinkListNode* qMoveFlag = nullptr;//移动标志位

	for (int num = length - 1; num >= 0; num--)
	{
		pAddNode = (LinkListNode*)malloc(sizeof(LinkListNode));
		pAddNode->data = arr[num];

		pAddNode->pNext = qMoveFlag;//是的新加入的节点传入了上一个节点
		qMoveFlag = pAddNode;//让q指向当前的节点
	}
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = qMoveFlag;

	return pHead;
}

//----------------------------------------------------------
LinkListNode* Create_Front3_LkList(ElemType arr[], int length)
{
	LinkListNode* pHead = nullptr;//头节点
	LinkListNode* pAddNode = nullptr;//新增节点
	pHead = (LinkListNode*)malloc(sizeof(LinkListNode));
	pHead->pNext = nullptr;

	for (int num = length - 1; num >= 0; num--)
	{
		pAddNode = (LinkListNode*)malloc(sizeof(LinkListNode));
		pAddNode->data = arr[num];

		pAddNode->pNext = pHead->pNext;//新结点 指向 头节点的下一个节点
		pHead->pNext = pAddNode;//头结点指向新节点
	}
	return pHead;
}

//----------------------------------------------------------
void Insert_After_LkList(LinkListNode* ptr, ElemType x)
{
	LinkListNode* s;
	s = (LinkListNode*)malloc(sizeof(LinkListNode));
	s->data = x;
	s->pNext = ptr->pNext;
	ptr->pNext = s;
}

//----------------------------------------------------------
void Insert_Before_LkList(LinkListNode* ptr, ElemType x)
{
	LinkListNode* s;
	s = (LinkListNode*)malloc(sizeof(LinkListNode));
	s->data = ptr->data;
	s->pNext = ptr->pNext;
	ptr->pNext = s;
	ptr->data = x;
}

//----------------------------------------------------------
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x)
{
	LinkListNode* s, * qPtr;
	s = (LinkListNode*)malloc(sizeof(LinkListNode));
	s->data = x;
	qPtr = pHead;//qPtr是用来代替pHead的移动的,ptr是目标节点
	while (qPtr->pNext != ptr)
		qPtr = qPtr->pNext;
	s->pNext = ptr;
	qPtr->pNext = s;
	//因为链表是单向的，虽然我知道当前节点是ptr
	//但是在语法层面上，我如果想知道ptr的前继节点只能从head遍历而来
	//查到了当前节点的前继，才能使用后插的方法完成节点的加入
}

//----------------------------------------------------------
LinkListNode* Delete_After_LkList(LinkListNode* ptr)
{
	//删除制定节点的后继节点
	LinkListNode* fptr;
	//假定我们的顺序表A-》B-》C,我们要删除的是A的后续节点B，A-》C
	fptr = ptr->pNext;// ptr是A，所以ptr的next是B，所以fptr是B
	ptr->pNext = fptr->pNext;//ptr是A，fptr是B，所以fptr的next是C，所以ptr-next就变成C
	return fptr;
}

//----------------------------------------------------------
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i)
{
	LinkListNode* ptr, * qPtr = nullptr;
	ptr = GetLinkListNode(pHead, i - 1);//找到i的前继节点
	if (ptr != nullptr && ptr->pNext != nullptr)
		qPtr = Delete_After_LkList(ptr);
	return qPtr;
}

//----------------------------------------------------------
void ShowLkList(LinkListNode* pHead)
{
	LinkListNode* p = pHead->pNext;
	while (p != nullptr)
	{
		printf("%d", p->data);
		p = p->pNext;
	}
}

//----------------------------------------------------------
int main_linkList(void) {
	ElemType MySeq[] = { 1,2,3,4,5 };
	LinkListNode* pHead = Create_Front3_LkList(MySeq, 5);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	LinkListNode* pPos = GetLinkListNode(pHead, 2);
	Insert_After_LkList(pPos, 999);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	Insert_Before_LkList(pHead, pPos, 666);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	Delete_After_LkList(pPos);
	//Delete_i_LkList(pHead, 2);
	printf("\n********显示当前单链表中的全部元素******\n");
	ShowLkList(pHead);
	printf("\nList Size:%d", GetSizeLinkList(pHead));
	getchar();
	return 0;
}

//----------------------------------------------------------
